package cn.whdream.datastructure.huffmancode;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import javax.swing.plaf.synth.SynthSpinnerUI;

import cn.whdream.PrettyPrintingMap;

/**
 * 
 * @author admin 压缩一个文件的全路径
 * TODO 哈夫曼有问题，需要重新学习补充知识  压缩png的文件反而变得更大了且会报错，bmp是会变得特别小的
 */
public class HuffmanCodeDemoforFile {
	private static Map<Byte, String> HuffmanCodes = new HashMap<>();
	//存储叶子结点的路径
	private static StringBuilder builder = new StringBuilder();
	public static void main(String[] args) throws Exception {
		zipFile("G://1.bmp", "G://test.zip");
		unZipFile("G://test.zip", "G://111.bmp");
	}
	
	public static void zipFile(String srcFile ,String dstFile) throws Exception {
		OutputStream os = null;
		ObjectOutputStream oos = null;
		FileInputStream is = null;
		is = new FileInputStream(srcFile);
		byte[] b = new byte[is.available()]; 
		is.read(b);
		byte[] huffmanBytes = huffmanZip(b);
		os = new FileOutputStream(dstFile); 
		oos = new ObjectOutputStream(os);
		//TODO 探究一下对象流写入多个对象是如何实现的，顺序如何保证
		oos.writeObject(huffmanBytes);
		oos.writeObject(HuffmanCodes);
		System.out.println("压缩完毕");
		
	}
	
	public static void unZipFile(String srcFile,String dstFile) throws IOException, ClassNotFoundException {
		InputStream is = null;
		ObjectInputStream ois = null;
		OutputStream os = null;
		is = new FileInputStream(srcFile);
		ois = new ObjectInputStream(is);
		os = new FileOutputStream(dstFile);
		byte[] huffmanBytes = (byte[]) ois.readObject();
		
		Map<Byte,String> huffmanCodes = (Map<Byte, String>) ois.readObject();
		//解码
		byte[] bytes = decode(huffmanCodes, huffmanBytes);
		os.write(bytes);
		System.out.println("解压完毕");
	}
	
	
	/**
	 * 
	 * @param huffmanCodes 编码表
	 * @param huffmanBytes 编码得到的数组
	 * @return 原来对应的数组
	 */
	private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < huffmanBytes.length; i++) {
			byte b = huffmanBytes[i];
			boolean isLast = (i == huffmanBytes.length -1);
			//不是最后一节，需要补高位
			sb.append(bytetoBitString(b, !isLast));
		}
		//把字符串安装指定的哈夫曼编码表
		//将编码表反转
		Map<String,Byte> decodeMap = new HashMap<>();
		for (Map.Entry<Byte,String> e : huffmanCodes.entrySet()) {
			decodeMap.put(e.getValue(), e.getKey());
		}
		List<Byte> list = new ArrayList<>();
		for (int i = 0; i < sb.length(); ) {
			int count = 1; //计数
			boolean flag = true;
			Byte b = null;
			while (flag) {
				String key = sb.substring(i,i+count);
				b = decodeMap.get(key);
				if (b == null) {
					count++;
				}else {
					//匹配到
					flag = false;
				}
			}
			list.add(b);
			i+= count;//i 直接移动到count
		}
		byte[] bs = new byte[list.size()];
		for(int i = 0; i< bs.length;i++) {
			bs[i] = list.get(i);
		}
		return bs;
	}
	/**
	 * 将byte转为二进制的字符串
	 * @param b 
	 * @param flag 标识是否需要补充高位
	 * @return 对应的 byte的二进制的字符串，返回的是补码
	 */
	private static String bytetoBitString(byte b, boolean flag) {
		int temp = b;
		//如果为正数，不满8位需要补高位
		if (flag) {
			temp |= 256;
		}
		//返回的是 二进制的补码
		String str = Integer.toBinaryString(temp);
		if (flag) {
			return str.substring(str.length() -8);
		}else {
			return str;
		}
	}
	
	/**
	 * 
	 * @param original 原始数据
	 * @return
	 */
	private static byte[] huffmanZip(byte[] original) {
		byte[] bytes = original;
		//根据node生成列表
		List<Node> list = getListNode(bytes); 
		//创建成哈夫曼树
		Node parent = creatHuffmanTree(list);
		//生成编码表
		getCodes(parent);
		System.out.println(new PrettyPrintingMap<Byte, String>(HuffmanCodes));
		//利用编码表将string进行转换
		byte[] huffman = zip(bytes,HuffmanCodes);
		return huffman;
	}
	/**
	 * 编码压缩成一个二进制codes
	 * @param bytes
	 * @param huffmanCodes
	 * @return 返回编码后的byte byte[]
	 */
	private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes) {
		//对原byte进行转换
		 StringBuilder sb = new StringBuilder();
		 //遍历bytes数组
		 for (byte b : bytes) {
			 sb.append(huffmanCodes.get(b));
		}
		 //System.out.println(sb.toString());
		 //将字符串转换成byte[]数组
		 int len = 0;
		 if (sb.length() % 8 == 0) {
			 len = sb.length() /8;	
		}else {
			len = sb.length() /8 + 1;
		}
		 byte[] by = new byte[len];
		 int index = 0;
		 for (int i = 0; i < sb.length(); i += 8) {
			String strbyte;
			if(i+8 > sb.length()) {
				strbyte = sb.substring(i);
			}else {
				strbyte = sb.substring(i,i+8);
			}
			by[index] = (byte) Integer.parseInt(strbyte,2);
			index++;
		}
		 return by;
	}
	
	/**
	 * 获取编码表
	 * @param root
	 * @return
	 */
	private static Map<Byte,String> getCodes(Node root) {
		if (root == null) {
			return null;
		}
		getCodes(root.left,"0",builder);
		getCodes(root.right,"1",builder);
		return HuffmanCodes;
	}
	
	private static void getCodes(Node node ,String code,StringBuilder stringBuilder) {
		//将上一次的stringBuilder继续
		StringBuilder sb2 = new StringBuilder(stringBuilder);
		sb2.append(code);
		if (node != null) {
			//非叶子结点,不断将路径进行记录，然后形成对应编码的 编码code
			if (node.data == null) {
				getCodes(node.left, "0", sb2);
				getCodes(node.right, "1", sb2);
			}else {
				HuffmanCodes.put(node.data, sb2.toString());
			}
		}
	}
	private static Node creatHuffmanTree(List<Node> list) {
		while(list.size() > 1) {
			Collections.sort(list);
			Node leftNode = list.get(0);
			Node rightNode = list.get(1);
			Node parent = new Node(null,leftNode.weight+rightNode.weight);
			parent.left = leftNode;
			parent.right = rightNode;
			//删除处理后的二叉树
			list.remove(leftNode);
			list.remove(rightNode);
			//将处理好的node重新加入list
			list.add(parent);
		}
		return list.get(0);
	}

	private static List<Node> getListNode(byte[] bytes) {
		List<Node> list = new ArrayList<HuffmanCodeDemoforFile.Node>();
		for (byte b : bytes) {
			Node key = new Node(b,1);
			if (list.contains(key)) {
				int index =list.indexOf(key);
				list.get(index).weight++;
			}else {
				list.add(key);
			}
		}
		return list;
	}

	private static class Node implements Comparable<Node>{
		public Byte data;
		int weight;
		Node left;
		Node right;
		
		public Node(Byte data) {
			super();
			this.data = data;
		}
		public Node(Byte data, int weight) {
			super();
			this.data = data;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
		@Override
		public String toString() {
			return "Node [data=" + data + ", weight=" + weight + "]";
		}
		
		public void preOrder() {
			System.out.println(this);
			if (left != null) {
				left.preOrder();
			}
			if (right != null) {
				right.preOrder();
			}
		}
		@Override
		public int hashCode() {
			return data.hashCode();
		}
		@Override
		public boolean equals(Object obj) {
			if(this == obj) {
				return true;
			}
			if (obj instanceof Node) {
				Node temp = (Node) obj;
				if(data == temp.data) {
					return true;
				}
			}
			return false;
		}
		
		
	}
	
}
